package com.sise.DFS;

import java.util.HashMap;
import java.util.HashSet;

/**
 *      827. 最大人工岛
 *
 *      给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
 *      返回执行此操作后，grid 中最大的岛屿面积是多少？
 *      岛屿 由一组上、下、左、右四个方向相连的 1 形成。
 *
 *      输入: grid = [[1, 0], [0, 1]]
 *      输出: 3
 *      解释: 将一格 0 变成 1，最终连通两个小岛得到面积为 3 的岛屿。
 *
 *      题解：
 *      对网格进行两次遍历，第一次遍历得到每个岛屿群的最大值，同时给岛屿群进行编号，形成 Map<岛屿编号 : 岛屿面积>，
 *      第二次便针对海洋进行遍历，获取海洋格子的上下左右，同时使用 Set 进行去重，防止海洋格子的邻居是同一个岛屿，导致同一个岛屿相加多次，
 *      Set 中存放的是 岛屿编号，后续对 Set 进行遍历，根据岛屿编号获取 岛屿面积，再将其相加。
 */
public class _827_largestIsland {
    public int largestIsland(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 1;
        }

        int result = 0;
        int index = 2;      // index表示岛屿的编号，0是海洋,1是陆地，从陆地从2开始遍历
        HashMap<Integer, Integer> indexAndAreas = new HashMap<>();      // 岛屿编号：岛屿面积

        /**
         *      计算每个岛屿的面积，并标记是第几个岛屿，将记录的信息存到 HashMap 中，便于后续 遍历海洋格子后合并
         */
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {                              // 遍历没有访问过的岛屿格子
                    int area = area(grid, i, j, index);             // 返回每个岛屿的面积，dfs
                    indexAndAreas.put(index, area);                 // 存入岛屿编号、岛屿面积
                    index++;                                        // 岛屿编号增加
                    result = Math.max(result, area);                // 记录最大的岛屿面积，这里的记录是为了下面的 if (result == 0) return 1;
                }
            }
        }

        if (result == 0) return 1;                                  // res = 0 表示没有陆地，那么造一块，则返回1即可

        /**
         *      遍历海洋格子，假设填充了这个格子，那么就把上下左右是陆地的格子所在的岛屿连接起来
         */
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {                                                  // 遍历海洋格子
                    HashSet<Integer> hashSet = findNeighbour(grid, i, j);               // 把上下左右邻居放入set去重
                    if (hashSet.size() < 1) continue;                                   // 如果海洋格子周围没有格子不必计算
                    int twoIsland = 1;                                                  // 填充这个格子，初始为1，这个变量记录合并岛屿后的面积
                    for (Integer num : hashSet) {
                        twoIsland += indexAndAreas.get(num);                            // 遍历 HashSet，将其上下左右的岛屿群相加后，再加上自己本身 +1
                    }
                    result = Math.max(result, twoIsland);                               // 比较得到最大的面积
                }
            }
        }
        return result;
    }


    /**
     *      对于海洋格子，找到上下左右，每个方向，都要确保有效 inArea 以及是陆地格子，则表示是该海洋格子的陆地邻居
     *
     *      这里使用的是 HashSet，目的是为了去重，以免海洋格子的周围恰好是 同一个岛屿群，而相加多次。
     *      下面的判断除了 检验是否出界，同时 grid[r - 1][c] != 0 检验不是为海洋格子
     */
    private HashSet<Integer> findNeighbour(int[][] grid, int r, int c) {
        HashSet<Integer> hashSet = new HashSet<>();
        if (inArea(grid, r - 1, c) && grid[r - 1][c] != 0) {
            hashSet.add(grid[r - 1][c]);
        }
        if (inArea(grid, r + 1, c) && grid[r + 1][c] != 0) {
            hashSet.add(grid[r + 1][c]);
        }
        if (inArea(grid, r, c - 1) && grid[r][c - 1] != 0) {
            hashSet.add(grid[r][c - 1]);
        }
        if (inArea(grid, r, c + 1) && grid[r][c + 1] != 0) {
            hashSet.add(grid[r][c + 1]);
        }
        return hashSet;
    }

    /**
     *      以该点为起点，填充 index 编号，标记属于那个岛群。同时经过 dfs 后，得到该岛屿的最大面积
     */
    private int area(int[][] grid, int r, int c, int index) {
        if (!inArea(grid, r, c)) {
            return 0;
        }

        if (grid[r][c] != 1) {          // 不为1，表示为海洋格子 或者 走过的陆地格子
            return 0;
        }

        grid[r][c] = index;             // 设置当前格子为某个岛屿编号

        return 1 + area(grid, r - 1, c, index)
                 + area(grid, r + 1, c, index)
                 + area(grid, r, c - 1, index)
                 + area(grid, r, c + 1, index);
    }

    /**
     *      判断当前位置是否出界
     */
    private boolean inArea(int[][] grid, int row, int col) {
        return row >= 0 && row < grid.length && col >= 0 && col < grid[0].length;
    }
}
